1. Field of the Invention
The present invention relates to a list type data storing and retrieving system for storing and retrieving list type data using a LISP language or the like.
2. Description of the Related Art
List type data using the LISP language or the like is used as a basic unit for notation of information especially in the field of artificial intelligence. List type data are respectively constituted by sets 11 to 15 each obtained by aligning a certain number of elements and putting them in parentheses, as shown in FIG. 1. In this list type data, symbols a and b represent constants and a symbol affixed with "?" represents a variable.
If a large amount of list type data described above is present, it takes a considerably long period of time to retrieve list type data to be retrieved and unifiable lists. For this reason, in a conventional system, candidates of unifiable list type data are retrieved prior to execution of unification. A system using discrimination nets is known as a system for selecting unifiable list type data candidates. In this system, the list type data shown in FIG. 1 is converted into list type data shown in FIG. 2, and elements in the list are sequentially discriminated from the first element. As a result, a tree structure shown in FIG. 3 is generated, and retrieval is performed by searching this tree structure. Such a tree structure is described in a literature--Charniak, Riesbeck, McDermott "ARTIFICIAL INTELLIGENCE PROGRAMMING"--entitled "Discrimination Nets With Variable".
According to the above-described tree structure, when a variable (element with "?") appears in the latter half of list type data, since list type data candidates are sequentially narrowed down, high-speed retrieval can be performed. However, if a variable is present in the first half of list type data, since all the nets of the tree structure must be retrieved, the retrieval efficiency is greatly degraded. More specifically, assume that list type data (a b ?p) is to be retrieved. This data is converted into data (#a #b #variable nil) as shown in FIG. 2, and this list type data is retrieved from a discrimination net of the tree structure shown in FIG. 3. The above data can be retrieved through the discrimination net of a path Pl.
If list type data to be retrieved has a format (?p ?q c), a converted list (#variable #variable #c nil) is generated. Since a variable is present in the first half of the list, all paths P1 to P5 of the tree structure must be retrieved. Therefore, a time required for retrieval is greatly prolonged.
In the above-described discrimation system using a tree structure, a considerably long period of time is required for retrieval depending on the position of a variable appearing in list type data.